package com.zsj.Tree;

import lombok.Data;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/4/14 14:11
 * @description 二叉搜索树
 */
@Data
@SuppressWarnings("all")
public class BinarySearchTree {

    public BSNode root;//根节点


    public static class BSNode {
        int key;
        Object value;
        BSNode left;
        BSNode right;

        public BSNode(int key) {
            this.key = key;
        }

        public BSNode(int key, Object value, BSNode left, BSNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }

        public BSNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return value.toString();
        }
    }

    /**
     * 根据key来搜索值
     *
     * @param key key
     * @return 返回的对象值
     */
    public Object get(int key) {
        return doGet(root, key);
    }

    //递归方式
    private Object doGet(BSNode node, int key) {
        if (node == null) return null;//没找到也是有可能的
        if (key == node.key) return node.value;
        else if (key < node.key) return doGet(node.left, key);
        else return doGet(node.right, key);
    }

    //非递归方式
    public Object doGetNoRecursion(int key) {
        BSNode node = root;
        while (node != null) {
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else return node.value;
        }
        return null;
    }


    /**
     * 搜最小值   最左边的叶子节点就是最小的
     *
     * @return 最小值
     */
    public Object min() {
        if (root == null) return null;
        BSNode cur = root;
        while (cur.left != null) {
            cur = cur.left;
        }
        return cur.value;
    }

    public Object min(boolean isR) {
        return doMin(root);
    }

    private Object doMin(BSNode node) {
        if (node == null) return null;
        if (node.left == null) return node.value;
        return doMin(node.left);
    }


    /**
     * 搜最大值 最右边的叶子节点就是最大的
     *
     * @return 最大值
     */
    public Object max() {
        if (root == null) return null;
        BSNode cur = root;
        while (cur.right != null) {
            cur = cur.right;
        }
        return cur.value;
    }

    /**
     * 往树中添加值
     * important!
     *
     * @param key   key
     * @param value 值
     */
    public void put(int key, Object value) {
        //key有了 就是更新操作 没有就添加
        BSNode cur = root;
        BSNode parent = null;
        while (cur != null) {
            //记录parent
            parent = cur;
            if (key < cur.key) {
                cur = cur.left;
            } else if (key > cur.key) {
                cur = cur.right;
            } else {
                //更新
                cur.value = value;
                return;
            }
        }
        if (parent == null) {
            //新增根节点
            root = new BSNode(key, value);
            return;
        }
        //到这里说明cur为null
        BSNode node = new BSNode(key, value);
        if (key < parent.key) parent.left = node;
        else parent.right = node;
    }


    /**
     * 二叉搜索树的排序
     * 其实就是一个中序遍历
     * 遍历出来根据key是自然有序的
     */
    public void iteration() {
        //就不使用递归了
        LinkedList<BSNode> stack = new LinkedList<>();
        BSNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                //继续往左边
                stack.push(cur);
                cur = cur.left;
            } else {
                //走右边
                BSNode pop = stack.pop();
                System.out.print(pop.key + "\t");
                cur = pop.right;
            }
        }
    }

    /**
     * 查找key是否存在
     *
     * @param key key
     * @return true存在 false不存在
     */
    public boolean containsKey(int key) {
        return get(key) != null;
    }

    /**
     * 查找关键字的前驱值
     *
     * @param key 关键字
     * @return 前驱值
     */
    public Object successor(int key) {
        //节点有左子树 那他的前驱值就是左子树的最大值
        //节点没有左子树 那他的前驱就是离他最近的祖先且比它小的值
        BSNode cur = root;
        BSNode ancestorFromLeft = null;//自左而来的祖先
        while (cur != null) {
            if (key < cur.key) {
                cur = cur.left;
            } else if (key > cur.key) {
                ancestorFromLeft = cur;//记录自左而来的节点
                cur = cur.right;
            } else {
                //说明找到了
                return cur;
            }
        }
        if (cur == null) return null;//如果为null 那它的前驱节点也是null
        if (cur.left != null) {
            //如果左子树不为null
            return getMaxNode(cur.left).value;
        } else {
            //需要找父节点的比它小的值
            //相当于从根节点开始取找他 每次如果是往right方向去找的可以记录一下
            return ancestorFromLeft != null ? ancestorFromLeft : null;
        }
    }

    /**
     * 查找某个节点树中最大的值
     *
     * @param node 节点
     * @return 最大节点
     */
    private BSNode getMaxNode(BSNode node) {
        BSNode cur = node;
        while (cur != null) {
            if (cur.right != null) {
                cur = cur.right;
            }
        }
        return cur;
    }

    private BSNode getNode(int key) {
        BSNode cur = root;
        while (cur != null) {
            if (key < cur.key) {
                cur = cur.left;
            } else if (key > cur.key) {
                cur = cur.right;
            } else {
                //说明找到了
                return cur;
            }
        }
        return null;//没找到
    }

    /**
     * 查找关键字的后驱值
     *
     * @param key 关键字
     * @return 后驱值
     */
    public BSNode predecessor(int key) {
        //节点有右子树 那他的前驱值就是左子树的最小值
        //节点没有右子树 那他的后驱就是ancestorFromRight.value
        BSNode cur = root;
        BSNode ancestorFromRight = null;//自右而来的祖先
        while (cur != null) {
            if (key < cur.key) {
                ancestorFromRight = cur;//记录自右而来的节点
                cur = cur.left;
            } else if (key > cur.key) {
                cur = cur.right;
            } else {
                //说明找到了
                return cur;
            }
        }
        if (cur == null) return null;//如果为null 那它的后驱节点也是null
        if (cur.right != null) {
            //如果右子树不为null
            return getMinNode(cur.left);
        } else {
            //需要找父节点的比它小的值
            //相当于从根节点开始取找他 每次如果是往right方向去找的可以记录一下
            return ancestorFromRight != null ? ancestorFromRight : null;
        }
    }

    private BSNode getMinNode(BSNode left) {
        BSNode cur = left;
        while (cur != null) {
            if (cur.left != null) cur = cur.left;
        }
        return cur;
    }

    /**
     * 根据关键字进行删除
     *
     * @param key 关键字
     * @return 对应节点值
     */
    public Object delete(int key) {
        BSNode cur = root;
        BSNode parent = null;
        while (cur != null) {
            if (key < cur.key) {
                //如果往左走了记录parent
                parent = cur;
                cur = cur.left;
            } else if (key > cur.key) {
                //同样的道理
                parent = cur;
                cur = cur.right;
            } else {
                //说明找到了
                //此时cur就是需要删除的节点
                break;
            }
        }
        if (cur == null) return null;

        //删除操作
        if (cur.left == null) {
            //左子树为空 但是右子树不为空
            shift(parent, cur, cur.right);
        } else if (cur.right == null) {
            //右子树为空 左子树不为空
            shift(parent, cur, cur.left);
        } else {
            //两边都有
            //将被删节点的后继节点转移给parent
            BSNode s = cur.right;
            //记录后继结点的父亲
            BSNode sp = cur;
            while (s.left != null) {
                sp = s;
                s = s.left;//找寻右子树中的最小值
            }
            if (sp != cur) {
                //说明后继节点的父亲不是被删除节点 也就是不相邻
                //代码执行到这里不可能再会有左孩子了....
                shift(sp, s, s.right);//这里太绝了
                s.right = cur.right;
            }
            //替换后继节点和被删除节点
            shift(parent, s, sp);
            s.left = cur.left;

        }
        return cur.value;
    }


    public Object deleteR(int key) {
        List<Object> list = new ArrayList<>();
        root = delete(root, key, list);
        return list.isEmpty() ? null : list.get(0);
    }

    /**
     * 删除节点 递归实现
     *
     * @param begin 开始删除的位置
     * @param key   删除的key
     * @return 删除剩下的节点
     */
    public BSNode delete(BSNode begin, int key, List<Object> list) {
        if (begin == null) return null;
        if (key < begin.key) {
            begin.left = delete(begin.left, key, list);
            return begin;
        }
        if (key > begin.key) {
            begin.right = delete(begin.right, key, list);
            return begin;
        }
        list.add(begin.value);
        //没有左孩子
        if (begin.left == null) {
            return begin.right;
        }
        //没有右孩子
        if (begin.right == null) {
            return begin.left;
        }
        BSNode s = begin.right;
        while (s.left != null) {
            s = s.left;
        }
        //后继节点的左孩子= 被删节点的左孩子
        delete(begin.right, s.key, new ArrayList<>());
        s.left = begin.left;
        return s;
    }

    /**
     * 转移关系
     *
     * @param parent 被删的父节点
     * @param delete 被删除节点
     * @param son    被删除的儿子节点 这里的儿子节点在调用此方法时已经决定了
     */
    private void shift(BSNode parent, BSNode delete, BSNode son) {
        if (parent == null) {
            //说明删除的是根节点
            root = son; //需要重新构建孩子的关系树
        } else if (delete == parent.left) {
            parent.left = son;
        } else parent.right = son;

    }


    /**
     * 找出比key小的所有节点信息
     *
     * @param key 指定key
     * @return 节点集合
     */
    public List<BSNode> less(int key) {
        //中序遍历
        ArrayList<BSNode> result = new ArrayList<>();
        BSNode cur = root;
        Stack<BSNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                BSNode pop = stack.pop();
                if (pop.key < key) result.add(pop);
                else break;
                cur = pop.right;
            }
        }
        return result;
    }

    /**
     * 找出比key大的所有节点信息
     *
     * @param key 指定key
     * @return 节点集合
     */
    public List<BSNode> greater(int key) {
        ArrayList<BSNode> result = new ArrayList<>();
        BSNode cur = root;
        Stack<BSNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                BSNode pop = stack.pop();
                if (pop.key > key) result.add(pop);
                cur = pop.right;
            }
        }
        return result;
    }

    /**
     * 找出在key1和key2之间的所有节点信息
     *
     * @param key  指定key
     * @param key2 指定key2
     * @return 节点集合
     */
    public List<BSNode> between(int key, int key2) {
        ArrayList<BSNode> result = new ArrayList<>();
        BSNode cur = root;
        Stack<BSNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                BSNode pop = stack.pop();
                if (pop.key >= key && pop.key <= key2) result.add(pop);
                if (pop.key > key2) break;
                cur = pop.right;
            }
        }
        return result;
    }

    /**
     * 找出比key大的所有节点信息
     * 反向中序遍历
     *
     * @param key 指定key
     * @return 节点集合
     */
    public List<BSNode> greaterReverse(int key) {
        ArrayList<BSNode> result = new ArrayList<>();
        BSNode cur = root;
        Stack<BSNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.right;
            } else {
                BSNode pop = stack.pop();
                if (pop.key > key) result.add(pop);
                else break;
                cur = pop.left;
            }
        }
        return result;
    }

}

